package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 被列覆盖的最多行数
 */

public class Code2397 {
    public static void main(String[] args) {
        int[][] matrix = {
                {0, 0, 0},
                {1, 0, 1},
                {0, 1, 1},
                {0, 0, 1}
        };
        int numSelect = 2;
        System.out.println(new Code2397().maximumRows(matrix, numSelect));  // 输出：2
    }

    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length;
        int n = matrix[0].length;

        // Step 1: 将每一行转换为一个整数掩码，表示哪些列是 1
        int[] rowMasks = new int[m];
        for (int i = 0; i < m; i++) {
            int mask = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    mask |= (1 << j);
                }
            }
            rowMasks[i] = mask;
        }

        // Step 2: 枚举所有从 n 列中选 numSelect 列的组合
        int maxCovered = 0;
        List<Integer> allMasks = generateAllMasks(n, numSelect);

        for (int selectedCols : allMasks) {
            int coveredRows = 0;
            for (int rowMask : rowMasks) {
                // 判断 rowMask 中的 1 是否全部在 selectedCols 中
                if ((rowMask & selectedCols) == rowMask) {
                    coveredRows++;
                }
            }
            maxCovered = Math.max(maxCovered, coveredRows);
        }

        return maxCovered;
    }

    // 生成所有 n 位中选 k 位的掩码组合（使用 bitmask 技巧）
    private List<Integer> generateAllMasks(int n, int k) {
        List<Integer> result = new ArrayList<>();
        int[] bits = new int[n];

        // 初始化掩码，前 k 个位置为 1
        Arrays.fill(bits, 0, k, 1);

        do {
            int mask = 0;
            for (int i = 0; i < n; i++) {
                if (bits[i] == 1) {
                    mask |= (1 << i);
                }
            }
            result.add(mask);
            // 使用 next permutation 生成下一个组合
        } while (nextCombination(bits));

        return result;
    }

    // 生成下一个组合（按字典序）
    private boolean nextCombination(int[] bits) {
        int n = bits.length;
        int i = n - 2;
        while (i >= 0 && bits[i] <= bits[i + 1]) {
            i--;
        }
        if (i < 0) return false;

        int j = n - 1;
        while (bits[j] >= bits[i]) {
            j--;
        }

        // swap bits[i] and bits[j]
        int temp = bits[i];
        bits[i] = bits[j];
        bits[j] = temp;

        // reverse suffix
        j = n - 1;
        while (i + 1 < j) {
            temp = bits[i + 1];
            bits[i + 1] = bits[j];
            bits[j] = temp;
            i++;
            j--;
        }

        return true;
    }
}
